package leetcode.D100.T3;

import java.util.HashMap;
import java.util.Map;

class Solution {
    // 一刷
    /*public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> map = new HashMap<>();
        int maxlen = 0, front = -1;
        for(int i=0; i<s.length(); ++i) {
            char x = s.charAt(i);
            if(!map.containsKey(x)) {
                map.put(x, -1);
            }
            int lastIndex = map.get(x);
            map.put(x, i);
            front = Math.max(front, lastIndex);
            maxlen = Math.max(maxlen, i - front);
        }
        return maxlen;
    }*/

    // 滑动窗口解法（一刷）
    /*public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> window = new HashMap<>();
        int left = 0, right = 0, maxlen = 0;
        boolean flag = true;
        while(right < s.length()) {
            char c = s.charAt(right++);
            if(window.containsKey(c)) {
                window.put(c, 2);
                flag = false;
            } else {
                window.put(c, 1);
                maxlen = Math.max(maxlen, right-left);
            }
            while(flag == false && left < right) {
                char d = s.charAt(left++);
                if(window.get(d) > 1) {
                    flag = true;
                    window.put(d, 1);
                } else {
                    window.remove(d);
                }
            }
        }
        return maxlen;
    }*/
    // 滑动窗口解法（二刷）
    /*public int lengthOfLongestSubstring(String s) {
        int left = 0, right = 0;
        int maxLen = 0;
        boolean flag = true;
        Map<Character, Integer> window = new HashMap<>();
        while(right < s.length()) {
            char c = s.charAt(right++);
            if(!window.containsKey(c)) {
                maxLen = Math.max(maxLen, right-left);
                window.put(c, 1);
            } else {
                flag = false;
                window.put(c, window.get(c) + 1);
            }
            while(flag == false) {
                char d = s.charAt(left++);
                if (window.get(d) == 1) {
                    window.remove(d);
                } else {
                    window.put(d, 1);
                    flag = true;
                }
            }
        }
        return maxLen;
    }*/

    // 三刷
    /*public int lengthOfLongestSubstring(String s) {
        int left = 0, right = 0, maxLen = 0;
        boolean flag = true;
        Map<Character, Integer> window = new HashMap<>();
        while(right < s.length()) {
            char c = s.charAt(right++);
            int origin = window.getOrDefault(c, 0);
            if(origin > 0) {
                flag = false;
            } else {
                maxLen = Integer.max(maxLen, right-left);
            }
            window.put(c, origin+1);
            while(flag == false) {
                char d = s.charAt(left++);
                int originVal = window.get(d);
                if(originVal > 1) {
                    flag = true;
                }
                window.put(d, originVal-1);
            }
        }
        return maxLen;
    }*/

    // 三刷
    public int lengthOfLongestSubstring(String s) {
        int result = 0, left = 0, right = 0;
        boolean valid = true;
        Map<Character, Integer> window = new HashMap<>();
        while(right < s.length()) {
            char c = s.charAt(right++);
            if(window.containsKey(c)) {
                valid = false;
            }
            window.put(c, window.getOrDefault(c, 0)+1);
            if (valid) {
                result = Math.max(result, (right-left));
            }
            while (!valid) {
                char d = s.charAt(left++);
                int origin = window.get(d);
                if (origin == 2) {
                    valid = true;
                    window.put(d, 1);
                } else {
                    window.remove(d);
                }
            }
        }
        return result;
    }
}
